package leetcode101.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code4
 * @description 1135. 最低成本联通所有城市
 * 想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。
 *
 * 给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost]
 * 表示将城市 city1 和城市 city2 连接所要的成本。
 * （连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。
 *
 * 返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。
 * 该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
 * 输出：6
 * 解释：
 * 选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。
 * 示例 2：
 *
 *
 *
 * 输入：N = 4, conections = [[1,2,3],[3,4,4]]
 * 输出：-1
 * 解释： 
 * 即使连通所有的边，也无法连接所有城市。
 *  
 *
 * 提示：
 *
 * 1 <= N <= 10000
 * 1 <= conections.length <= 10000
 * 1 <= conections[i][0], conections[i][1] <= N
 * 0 <= conections[i][2] <= 10^5
 * conections[i][0] != conections[i][1]
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-02 7:46
 */
public class Code4 {

    public static void main(String[] args) {
        int n = 3;
        int[][] connections = new int[][]{{1, 2, 5}, {1, 3, 6}, {2,3,1}};
//        int[][] connections = new int[][]{{1, 2, 3}, {3, 4, 4}};
        System.out.println(minimumCost(n, connections));
    }

    public static int minimumCost(int n, int[][] connections) {
        if (n == 1) {
            return 0;
        }
        int start = 1; // 选取1作为源点
        int res = 0; // 返回值
        int[] costs = new int[n + 1]; // 存储从已经联通的集合到其余顶点的距离
        List<Integer> connected = new ArrayList<>(); // 已经联通的结点集合
        connected.add(start);
        List<Integer> unConnected = new ArrayList<>(); // 尚未联通的结点集合
        for (int i = 2; i <= n; i++) {
            unConnected.add(i);
        }

        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                graph[i][j] = -1;
            }
        }
        for (int[] connection : connections) {
            graph[connection[0]][connection[1]] = connection[2];
            graph[connection[1]][connection[0]] = connection[2];
        }

        while (!unConnected.isEmpty()) {
            int min = Integer.MAX_VALUE;
            Integer to = 0;
            for (int i = 0; i < connected.size(); i++) {
                for (int j = 0; j < unConnected.size(); j++) {
                    int distance = graph[connected.get(i)][unConnected.get(j)]; // 计算联通集合中i到非联通集合中j的距离
                    if (distance < min && distance != -1) {
                        min = distance;
                        to = unConnected.get(j);
                    }
                }
            }
            if (min == Integer.MAX_VALUE) {
                return res = -1;
            }
            costs[to] = min;
            unConnected.remove(to);
            connected.add(to);
        }
        for (int i = 1; i < costs.length; i++) {
            res += costs[i];
        }
        return res;
    }

}
